package solution;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-04-06
 * Time: 17:51
 */

//https://leetcode.cn/problems/word-break/submissions/421862769/
class Solution5 {
    public boolean wordBreak(String s, List<String> wordDict) {
        //转为哈希表，方便查找
        Set<String> wordDictSet = new HashSet<>(wordDict);
        //dp[i] 表示[0, i)的字符串拆分成单词能在wordDictSet中找到
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                //[0, j) 和 [j, i) 同时为true
                //才满足dp[i]为true的条件
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;//dp[i]已为true，没必要继续判断了
                }
            }
        }
        return dp[n];
    }
}


